package algorithm.leetcode;

import java.util.HashSet;
import java.util.Set;

/**
 * @author wuwen
 * @since 2023/12/6
 */
public class NO3_无重复字符的最大子串 {
    public static void main(String[] args) {
        SolutionPerformance executable = new SolutionPerformance();
        System.out.println(executable.lengthOfLongestSubstringFastest("abcdeafghi"));
    }


    static class Solution {
        public int lengthOfLongestSubstring(String s) {
            int answer = 0;
            char[] str = s.toCharArray();
            Set<Character> window = new HashSet<>();
            int left = 0, right = 0;

            while (right < str.length) {
                // 判断窗口中有无数据
                if (!window.contains(str[right])) {
                    window.add(str[right]);
                    answer = Math.max(answer, window.size());
                    right++;
                } else {
                    window.remove(str[left]);
                    left++;
                }
            }

            return answer;
        }
    }

    static class SolutionPerformance {

        /**
         * 在评论区看到的方法
         * 其实在for循环中，就是在看当前的start到end（左右指针）区间中有没有重复的字符，如果有的话，就直接
         * 将左指针指向了左指针的右边，以此来规避掉重复的位置。他的去重并没有使用集合，所以速度会快很多
         */
        public int lengthOfLongestSubstringFastest(String deal) {
            int answer = 0, n = deal.length();
            int left = 0, right = 0;
            while (right < n) {
                // 发现有重复字符时，可以直接把左指针移动到重复字符的下一个位置
                for (int i = left; i < right; i++) {
                    if (deal.charAt(i) == deal.charAt(right)) {
                        left = i + 1;
                        break;
                    }
                }
                answer = Math.max(answer, right - left + 1);
                right++;
            }
            return answer;
        }

        public int lengthOfLongestSubstring(String s) {
            // 使用Set来进行去重, 以及左右指针，都从零开始
            Set<Character> distincter = new HashSet<>();
            int left, right = 0, answer = 0;
            char[] handle = s.toCharArray();
            for (left = 0; left < handle.length; left++) {
                // 每次默认移除最左边的一个
                if (left != 0) {
                    distincter.remove(handle[left - 1]);
                }
                while (right < handle.length && !distincter.contains(handle[right])) {
                    distincter.add(handle[right]);
                    right++;
                }
                answer = Math.max(answer, right - left);
            }
            return answer;
        }

    }


    static class SolutionSelf {
        public int lengthOfLongestSubstring(String s) {
            Set<Character> container = new HashSet<>();
            int answer = 0, left = 0, right = 0;
            char[] arr = s.toCharArray();
            for (left = 0; left < arr.length; left++) {
                if (left != 0) {
                    container.remove(arr[left - 1]);
                }
                while (right < arr.length && !container.contains(arr[right])) {
                    container.add(arr[right]);
                    right++;
                }
                answer = Math.max(answer, container.size());
            }
            return answer;
        }
    }
}